package 力扣._7022_限制条件下元素之间的最小绝对差;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Solution3 {
    static class NumandIndex {
        int num;
        int index;

        public NumandIndex(int num, int index) {
            this.num = num;
            this.index = index;
        }
    }

    public int minAbsoluteDifference(List<Integer> nums, int x) {
        int min = Integer.MAX_VALUE;
        List<NumandIndex> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            list.add(new NumandIndex(nums.get(i), i));
        }
        list.sort(Comparator.comparingInt(o -> o.num));

        PriorityQueue<NumandIndex> leftQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o.index));
        PriorityQueue<NumandIndex> rightQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o.index));

        for (int i = 0; i < list.size(); i++) {
            while (!leftQueue.isEmpty() && leftQueue.peek().index + x <= i) {
                leftQueue.poll();
            }
            while (!rightQueue.isEmpty() && rightQueue.peek().index - x >= i) {
                rightQueue.poll();
            }

            while (!leftQueue.isEmpty() && leftQueue.peek().num <= list.get(i).num) {
                min = Math.min(min, Math.abs(leftQueue.peek().num - list.get(i).num));
                leftQueue.poll();
            }
            while (!rightQueue.isEmpty() && rightQueue.peek().num >= list.get(i).num) {
                min = Math.min(min, Math.abs(rightQueue.peek().num - list.get(i).num));
                rightQueue.poll();
            }

            leftQueue.add(list.get(i));
            rightQueue.add(list.get(i));
        }
        return min;
    }

}
